package com.example.algorithm.array;

// 一个数组，除一个元素外其它都是两两相等，求那个元素?

// 补充知识：
// ^符号，中文名称之为异或，是一种位运算。运算时先将左右两边的数换为二进制。然后，上下对齐写这，然后，同位的相同就得0，不同就得1(口诀记忆：异的得1，简称异1，谐音一衣)。最后，再将得到的值，转换为十进制。
//
//案例：
//9 二进制：1 0 0 1
//2 二进制：0 0 1 0
//9^2 结果：1 0 1 1 转换为十进制：8+2+1=11
//
//解析本题：
//比如，一个数组是{3, 1, 3, 2, 4, 2, 1}，那么，为什么异或运算最终能找出1这个值呢？因为，异或运算有如下性质：
//1，重要的性质是自反性：“A^B^B=A”。
// 自反性是说，对一个值连续两次进行异或操作，得到的结果是原始值本身。
// 另外，我们可知，B^B，得到的结果是0，因为你每个位置都一样啊，那自然相同的就得到0嘛。而A^0的话，更具异或的定义，任何值与0异或，都是原始值。那么，很自然，A^B^B=A。
// 从另一个角度来解释的话，A先后两次异或B，所以异或操作被抵消了，所以最后结果还是A 。
// 另外，异或操作和乘法操作的性质有些一样，满足，结合律、交换律等，所以，下面例子中的res = 0^3^1^3^2^4^2^1，它可以变成下面例子中的res = 0^(3^3)^(2^2)^(1^1)^4 = 0^4 = 4;所以，利用异或的特性，常常能够在一堆double中找出唯一一个single
// 2，任何数和0进行异或运算，都是该数本身。
//所以，当res的初始值0和任何两两相同的数异或之后，还是0。然后0再和落单的数异或，得到那个落单的数。
public class FindSingleItemInArrayTest {

    public static int find1From2(int[] a) {
        int len = a.length,
                res = 0;
        for (int i = 0; i < len; i++) {
            // {3, 1, 3, 2, 4, 2, 1}
            res = res ^ a[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 3, 2, 4, 2, 1};
        int res = find1From2(arr);
        System.out.println("The single num is:" + res);
    }
}


